package cm.unit2.theme3;

import cm.commom.TreeLinkNode;

public class TreeLinkNodeGetNext {
	
	public TreeLinkNode GetNext(TreeLinkNode pNode) {
		// 1.判断当前是否为根节点
		if(pNode.next==null) {
			// 2 判断是否有右子节点
			if (pNode.right!=null) {
				if(pNode.right.left!=null) {
					pNode = pNode.right.left;
					while(pNode.left!=null){
						 pNode = pNode.left;
					}
					return pNode;
				}else {
					return pNode.right;
				}
				
			}
			else {
				return null;
			}
		}
		else {
			// 2 判断是否有右子节点
			if (pNode.right!=null) {
				if(pNode.right.left!=null) {
					pNode = pNode.right.left;
				}
				while(pNode.left!=null){
					 pNode = pNode.left;
				}
				return pNode;
			}
			else {
				// 3 判段当前节点否为父节点的左子节点
				if (pNode.next.left==pNode) {
					return pNode.next;
				}else {
					// 4没有右子树
					if(pNode.right==null) {
						pNode = pNode.next;
						if(pNode.next.left==pNode) {
							return pNode.next;
						}else {
							return null;
						}
					}else {
						// 只有根节点
						return null;
					}
				}
			} 
		}
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}

}
